package C059;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c01
 * Package: C059
 * Description: https://leetcode.cn/problems/course-schedule-ii/description/ 课程表 拓扑排序模板
 *
 * @Author BCXJ
 * @Create 2025/5/5 22:43
 * @Version 1.0
 * @Since 1.0
 */
public class c01_01 {
    public static void main(String[] args) {
//        int[][] arr = {{1,0},{2,0},{3,1},{3,2}};
//        int[][] arr = {{0, 1}, {1, 2}, {1, 0}};
        //int[][] arr = {{0, 1}};
        int[][] arr = {{0, 1}, {1, 0}, {2, 0}};
        System.out.println(Arrays.toString(new c01_01().findOrder(3, arr)));
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        init(numCourses, prerequisites.length);

        for (int[] prerequisite : prerequisites) {
            addEdge(prerequisite[1], prerequisite[0]);
        }

        // 入度表进行统计
        for (int i = 0; i < inDegree.length; i++) {
            if(inDegree[i] == 0) {
                queue[r++] = i;
            }
        }

        // list 遍历返回结果
        return list();
    }

    // 前式链向星
    int n , m; // 边数，点数
    int[] head;
    int[] next;
    int[] tos;
    int[] inDegree; // 入度
    int cnt; // 边数
    // 初始化
    void init(int n, int m) {
        cnt = 1;
        this.n = n;
        this.m = m;
        head = new int[n];
        next = new int[m + 1];
        tos = new int[m + 1];
        inDegree = new int[n];
        queue = new int[n];
    }

    // 边加入
    void addEdge(int from , int to) {
        next[cnt] = head[from];  // next 指向自己的兄弟边
        tos[cnt] = to; // to 设置边指向的 点
        head[from] = cnt ++; // 点指向的第一条边
        inDegree[to]++; // 入度修改
    }


    // 队列的基本设置
    int[] queue;
    int l = 0, r = 0;
    // 遍历
    int[] list() {
        int curNode, curEdge;
        while (l < r) {
            curNode = queue[l ++];
            curEdge = head[curNode];
            // 遍历
            while(curEdge != 0 ) {
                inDegree[tos[curEdge]] --;
                if(inDegree[tos[curEdge]] == 0) {
                    queue[r++] = tos[curEdge];
                }
                curEdge = next[curEdge];
            }
        }
        return r == (n) ? queue : new int[]{};
    }

}
